package com.leetcode.partition6;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author `RKC`
 * @date 2021/11/8 18:16
 */
public class LC525连续数组 {

    public static int findMaxLength(int[] nums) {
        int ans = 0;
        Map<Integer, Integer> pos = new HashMap<>();
        pos.put(0, 0);
        int[] prefix = new int[nums.length + 1];
        //0变成-1，相等的条件就变成了差值为0
        nums = Arrays.stream(nums).map(val -> val == 1 ? 1 : -1).toArray();
        for (int i = 1; i <= nums.length; i++) {
            prefix[i] += prefix[i - 1] + nums[i - 1];
        }
        for (int i = 1; i <= nums.length; i++) {
            if (pos.containsKey(prefix[i])) {
                ans = Math.max(ans, i - pos.get(prefix[i]));
            } else {
                pos.put(prefix[i], i);
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] nums = {0, 1, 0, 1, 0};
        System.out.println(findMaxLength(nums));
    }
}
